\documentclass[mathserif]{beamer}
\usepackage[english]{babel}
\usepackage{float}
\usepackage{graphicx}
\usepackage{listings}
 \usepackage{multirow}
%\usepackage[footnotesize,bf]{caption}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
 \usepackage{color}
 \usepackage{xcolor}
 \usepackage[12pt]{moresize}
\usetheme{Darmstadt} % THIS IS THE THEME APPLIED TO THE SLIDES. IT CAN BE CHANGED

%ALTERNATIVES THEMES: Singapore, Darmstadt, Dresden, Antilopes

%\beamertemplateshadingbackground{blue!5}{white!10}
\usefonttheme{structurebold}

%COLORS USED IN THE SLIDES
\setbeamercolor*{author in head/foot}{parent=palette tertiary}
\setbeamercolor*{title in head/foot}{parent=palette secondary}
\setbeamercolor*{date in head/foot}{parent=palette primary}
\setbeamercolor*{section in head/foot}{parent=palette tertiary}
\setbeamercolor*{subsection in head/foot}{parent=palette primary}

%CONFIGURATION OF THE THREE BLOCKS IN THE FOOTER
\defbeamertemplate*{footline}{infolines theme}
{
  \leavevmode%
  \hbox{%
  \begin{beamercolorbox}[wd=.5\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
    \usebeamerfont{author in head/foot}\insertshortauthor
  \end{beamercolorbox}%
  \begin{beamercolorbox}[wd=.25\paperwidth,ht=2.25ex,dp=1ex,center]{title in head/foot}%
    \usebeamerfont{title in head/foot}\insertshorttitle
  \end{beamercolorbox}%
  \begin{beamercolorbox}[wd=.25\paperwidth,ht=2.25ex,dp=1ex,right]{date in head/foot}%
    \usebeamerfont{date in head/foot}\insertshortdate{}\hspace*{2em}
    \insertframenumber{} di \inserttotalframenumber\hspace*{2ex} 
  \end{beamercolorbox}}%
  \vskip0pt%
}


%\begin{tabular}{p{5cm}p{5cm}}
%		\begin{center}{\footnotesize Supervisor:}\\Name of Supervisor\end{center}&\begin{center}%{\footnotesize Student:}\\Name of Student\end{center}
%	\end{tabular}


\mode<presentation>

%colori
\definecolor{green}{rgb}{0.78,0.86,0.57} 
\definecolor{blue}{rgb}{0.51,0.79,0.83} 
\definecolor{purple}{rgb}{0.67,0.65,0.73}
\definecolor{grey}{rgb}{0.87,0.91,0.92}
\setbeamercolor{structure}{fg=blue}


%To set the listing package 
\lstset{ %
  language=Java,                % the language of the code
  basicstyle=\scriptsize,           % the size of the fonts that are used for the code
  numbers=left,                   % where to put the line-numbers
  numberstyle=\tiny\color{gray},  % the style that is used for the line-numbers
  stepnumber=1,                   % the step between two line-numbers. If it's 1, each line 
                                  % will be numbered
  numbersep=5pt,                  % how far the line-numbers are from the code
  backgroundcolor=\color{white},      % choose the background color. You must add \usepackage{color}
  showspaces=false,               % show spaces adding particular underscores
  showstringspaces=false,         % underline spaces within strings
  showtabs=false,                 % show tabs within strings adding particular underscores
  frame=shadowbox,                   % adds a frame around the code
  rulecolor=\color{black},        % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. commens (green here))
  tabsize=2,                      % sets default tabsize to 2 spaces
  captionpos=b,                   % sets the caption-position to bottom
  breaklines=true,                % sets automatic line breaking
  breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
 % title=\lstname,                   % show the filename of files included with \lstinputlisting;
                                  % also try caption instead of title
  keywordstyle=\color{magenta},          % keyword style
  commentstyle=\color{blue},       % comment style
  stringstyle=\color{red},         % string literal style
  escapeinside={\%*}{*)},            % if you want to add a comment within your code
  morekeywords={*,...}               % if you want to add more keywords to the set
}



%OTHER CONFIGURATION COLORS YOU DON'T NEED TO TAKE CARE ABOUT

% colori delle barre (scrivendo blue!20 si ha blue trasparente all'80% scrivendo blue!50!black si ha un colore a metà col nero)
%\setbeamercolor{palette primary}{fg=black,bg=green}
%\setbeamercolor{palette secondary}{fg=black,bg=purple}
%\setbeamercolor{palette tertiary}{fg=black,bg=blue}
%\setbeamercolor{palette quaternary}{fg=black,bg=grey}
%\setbeamercolor{titlelike}{parent=palette quaternary}

% \setbeamercolor{block title}{}
% \setbeamercolor{block title alerted}{use=alerted text,fg=blue,bg=alerted text.fg!75!bg}
% \setbeamercolor{block title example}{use=example text,fg=blue,bg=example text.fg!75!bg}
% \setbeamercolor{block body}{parent=normal text,use=block title,bg=block title.bg!25!bg}
%%\setbeamercolor{block body alerted}{parent=normal text,use=block title alerted,bg=block title alerted.bg!25!bg}
%%\setbeamercolor{block body example}{parent=normal text,use=block title example,bg=block title example.bg!25!bg}

% \setbeamercolor{sidebar}{}
 %%\setbeamercolor{palette sidebar primary}{fg=black}
 %%\setbeamercolor{palette sidebar secondary}{fg=black}
 %%\setbeamercolor{palette sidebar tertiary}{fg=black}
 %%\setbeamercolor{palette sidebar quaternary}{fg=black}

\setbeamertemplate{navigation symbols}{} % TO REMOVE THE NAVIGATION PANEL
\setbeamertemplate{caption}[numbered]

% \setbeamertemplate{background}{%
% 	\parbox[c][\paperheight]{\paperwidth}{%
% 		\vfill \hfill
% 		\includegraphics[width=0.8\paperwidth,height=0.8\paperheight]{pics/struttura-pdf.eps}
% 		\hfill \vfill
% 	}
% }

% \hypersetup{
% 	colorlinks=true,% false: boxed links; true: colored links
% 	linkcolor=black,% color of internal links
% 	urlcolor=black,% color of external links
% 	anchorcolor = black,
% 	citecolor = black
% }



%FOOTER
\title{Covana} 
\author{Anas Alzoghbi, Victor A. Arrascue Ayala}
\institute{University of Freiburg}
\date{22.02.2012}

%#####################
%#####################
%#####################
%HERE IS THE BEGINNING OF THE DOCUMENT
%#####################
%#####################
%#####################



\begin{document}

\renewcommand{\inserttotalframenumber}{29} %We have to manually insert the last slide

%FIRST SLIDE (BTW. FRAME = SLIDE IN LATEX)
\frame{
\begin{center}
	\vspace{2em}
%	\includegraphics[width=10cm]{pics/title2.png}\\ %THIS COMMAND INCLUDES THE IMAGE title2.png
	\begin{block}{}
	\begin{center}
	\Large Covana: Precise Identification of Problems for Structural Test Generation
	\end{center}
	\end{block}
	\vspace{2em}
	\textbf{\large University of Freiburg}\\
	\begin{footnotesize}	
		February 22th, 2012\\
	\end{footnotesize}
	\vspace{2em}
	%{\footnotesize by}\\
	Anas Alzoghbi - Victor A. Arrascue Ayala
\end{center}
}

%SUMMARY
\section{Outline}
\frame{
\frametitle{Outline}
\begin{enumerate}
\item Preliminaries
\begin{itemize}
\item Overview of Software Testing
\item Goals and Tools
\end{itemize}
\item Analysis
\begin{itemize}
\item Limitations
\end{itemize}
\item Solution
\begin{itemize}
\item Covana
\end{itemize}
\item Results
\item Assessment
\end{enumerate}
}

% \frame
% {
% \frametitle{Sommario}
% \begin{enumerate}
% \item \textcolor{blue}{\textbf{Dominio applicativo}}
% 	\begin{itemize}
% 	\item Tecnologie e processi aziendali
% 	\end{itemize}
% \item \textcolor{blue}{\textbf{Progetto di stage}}
% 	\begin{itemize}
% 	\item Il problema del ciclo passivo dei documenti
% 	\item Problematiche dei PDF
% 	\end{itemize}
% \item \textcolor{blue}{\textbf{Attività di stage}}
% 	\begin{itemize}
% 	\item Individuazione di una libreria
% 	\item La grammatica dei PDF
% 	\item Affidabilità del dato estratto
% 	\end{itemize}
% \item \textcolor{blue}{\textbf{Valutazione retrospettiva}}
% 	\begin{itemize}
% 	\item Codice prodotto e documentazione allegata
% 	\item Preventivo e consuntivo
% 	\item Conclusioni
% 	\end{itemize}
% \end{enumerate}
% }

%SECTION PRELIMINARIES
\section{Preliminaries}
\subsection{Overview of Software Testing}
\frame{
\frametitle{Software Testing}
IS0 9000
\begin{itemize}
\item \textit{{\bf verification} is confirmation by examination and through provision of objective evidence that specified requirements have been fulfilled}
\item \textit{{\bf validation} is confirmation by examination and through provision of objective evidence that the requirements for a specific intended use or application have been fulfilled}
\end{itemize}
\vspace{0.3cm}
problems$^{\textbf{{[}1{]}}}$
\begin{itemize}
\item billions of dollars
\begin{itemize}
\item 50\% of development's cost
\end{itemize}
\item poor software testing infrastructure
\begin{itemize}
\item software failures
\end{itemize}
\end{itemize}
}
\frame{
\frametitle{Unit Testing}
\textit{{\bf Def.} Unit is the smallest testable part of an application}\\
\vspace{0.5cm}
\begin{itemize}
\item applies to individual components
\item ensures that the algorithms and logic are correct
\item approx. 2/3 or defects are identified
\begin{itemize}
\item  (50\% from white-box structural tests)
\end{itemize}
\item hard and expensive 
\begin{itemize}
\item simulation of external environment of a software application
\end{itemize}
\end{itemize}

}

\subsection{Goals and Tools}
\frame{
\frametitle{High Structural Coverage}
{\bf Def.} \textit{Measurement of structural coverage of code is a mean of assessing the thoroughness of testing$^{\textbf{{[}2{]}}}$} \\
\begin{itemize}
\item {\bf statement coverage}: s/S, where\\
s = number of statements executed at least once\\
S = Total number of executable statements
\item {\bf branch coverage}: d/D, where\\
d = number of decision outcomes evaluated at least once\\
D = Total number of decision outcomes\\
%Verifies each branch of the control flow\\
%To achieve 100\% decision coverage, each condition controlling branching of the code has to evaluate to both true and false.
\item {\bf other criteria....}
\end{itemize}
}
%REFERENCES:
%http://www.math.unipd.it/~tullio/IS-1/Dispense_2003/Software_Testing_Metrics.htm

\frame{
\frametitle{Automated Test Generation$^{\textbf{{[}3{]}}}$}
\begin{columns}
\column{.4\textwidth}
{\bf Def.} \textit{The management and performance of test activities, to include the development and execution of test scripts so as to verify test requirements, using an automated test tool}
\column{.65\textwidth}
\begin{figure}[h!] 
\centering
  \includegraphics[scale=1]{pics/ATML.eps}
  \caption{a structured approach for the implementation of automated testing}
\end{figure}
\end{columns}
}

%REFERENCES:
%Elfriede Dustin, et al.: Automated Software Testing. Addison Wesley, 1999, ISBN 0-20143-287-0

\frame{
\frametitle{Automated Test Generation Tools}
\begin{itemize}
\item{\bf  test-case generation}
\begin{itemize}
\item set of conditions of a software system
\end{itemize}
\item {\bf tasks}
\begin{itemize}
\item test of data values
\item test of user interface
\item volume testing
\end{itemize}
\item {\bf  statistics generation}
\begin{itemize}
\item code complexity
\item test logs
\end{itemize}
\item {\bf code coverage analyzers}
\end{itemize}
}

\frame{
\frametitle{Automated Test Generation Tools}
\begin{figure}[h!] 
\centering
  \includegraphics[scale=1]{pics/SeleniumCoverage.eps}
  \caption{coverage report generated by Cobertura (open source)}
\end{figure}
}


\frame{
\frametitle{Dynamic Symbolic Execution (DSE)}
\begin{figure}[h!] 
\centering
  \includegraphics[scale=1]{pics/dse.eps}
  \caption{DSE conceptual diagram}
\end{figure}
%Approach ('04) for generation of test-cases:
%\begin{enumerate}
%\item Identifies the input variables
%\item Starts with a concrete execution on arbitrary input
%\item Symbolic execution with symbolic variables generates the symbolic constraints
%\item All the execution paths are visited (the last path condition is negated and the constraint solver invoked)
%\item A constraint solver find values for the input variables given the complete set of symbolic variable values and path conditions constructed during symbolic execution
%\item User defines the limit on the number of loop iterations (depth-limited search)
%\end{enumerate}
}
%REFERENCES:
%EWilliams, Nicky; Bruno Marre, Patricia Mouy, Muriel Roger (2005). "PathCrawler: Automatic Generation of Path Tests by Combining Static and Dynamic Analysis". Dependable Computing - EDCC-5, 5th European Dependable Computing Conference, Budapest, Hungary, April 20–22, 2005, Proceedings. Springer. pp. 281–292. ISBN 3-540-25723-3.
%http://132.167.192.79/labos/fr/LSL/test/docs/gb/edcc05.pdf

\frame{
\frametitle{DSE - Example$^{\textbf{{[}4{]}}}$}
\begin{columns}
\column[t]{.5\textwidth}
\begin{center}
\lstinputlisting{dseExample.java}
\end{center}
\column[t]{.5\textwidth}
\begin{figure}[h!] 
\centering
  \includegraphics[scale=1]{pics/paths.eps}
  \caption{execution path tree}
\end{figure}
\end{columns}
}


\section{Analysis}
\subsection{Limitations}
\frame{
\frametitle{Why cannot we achieve higher structural coverage?}
{\bf External-Method-Call Problem (EMCP)}\\
EMCs calls
\begin{itemize}
\item used in decision points
\item throw exceptions
\end{itemize}
\vspace{0.5cm}
{\bf Object-creation Problem (OCP)}\\
The tool
\begin{itemize}
\item cannot produce desirable object states
\end{itemize}
}

\frame{
\frametitle{External-Method-Call Problem (EMCP)}
\begin{tabular}{c} 
\lstinputlisting[basicstyle=\ssmall, numbersep=10pt]{emcpExample.java}
\end{tabular}
}


\frame{
\frametitle{Object-creation Problem (OCP)}
\begin{tabular}{c} 
\lstinputlisting[basicstyle=\ssmall, numbersep=10pt]{ocpExample.java}
\end{tabular}
}


\section{Solution}

\subsection{Covana}
\frame{
\frametitle{Covana overview}
\begin{figure}[h!] 
\centering
  \includegraphics[scale=1]{pics/CovanaConceptual.eps}
  \caption{covana's conceptual diagram}
\end{figure}
}

\frame{
\frametitle{Problem Candidate Identification}
\begin{figure}[h!] 
\centering
  \includegraphics[scale=1]{pics/Step1.eps}
  \caption{covana's 1$^{st}$ stage}
\end{figure}
}

\frame{
\frametitle{Problem Candidate Identification}
\begin{itemize}
\item {Let the DSE engine execute PUT with generated test inputs symbolically}\\
\item {Monitor triggered events by DSE (method entry, method exit)}\\
\item {Specify different types of problem candidates depending on the events}\\
\end{itemize}
}

\frame{
\frametitle{Problem Candidate Identification}
 {\bf Identifying EMCP Candidates}\\
\begin{itemize}
\item {Method exit event provides method instrumentation information}\\
\item {A method call is EMCP candidate if it is not instrumented by DSE}\\
\item {Consider only the external method calls which arguments have data dependencies on program inputs}\\
\end{itemize}
}

\frame{
\frametitle{Problem Candidate Identification}
 {\bf Identifying OCP Candidates}\\
\begin{itemize}
\item {Method entry event is triggered when test inputs are used as arguments}\\
\item {All non-primitive inputs and their non-primitive fields as OCP candidates}\\
\item {Ignore primitive inputs }\\
\end{itemize}
}
\frame{
\frametitle{Forward Symbolic Execution}
\begin{figure}[h!] 
\centering
  \includegraphics[scale=1]{pics/Step2.eps}
  \caption{covana's 2$^{nd}$ stage}
\end{figure}
}
\frame{
\frametitle{Forward Symbolic Execution}
Second stage:
\begin{itemize}
\item {Assign symbolic values to elements of problem candidates from the previous step}
\item {Leverage the DSE engine to perform Symbolic Execution, and:}
\begin{itemize}
\item {Looking for symbolic expressions of problem candidates in predicates of (partially covered) branch statements}
\item {catching thrown exceptions and forward them to the next step together with their stack trace }\\
\end{itemize}
\end{itemize}
}
\frame{
\frametitle{Data Dependency Analysis}
\begin{figure}[h!] 
\centering
 \includegraphics[scale=1]{pics/Step3.eps}
	  \caption{covana's 3$^{rd}$ stage}
\end{figure}
}
\frame{
\frametitle{Data Dependency Analysis}
 {\bf EMCP Analysis}\\
\begin{itemize}
\item{Data dependency of the predicates of a partially covered branch statements on the return value of a problem candidates}
\lstinputlisting[basicstyle=\tiny, numbersep=10pt]{ddaCode.java}
\item{Analyze the method calls from the stack trace of exceptions}
\end{itemize}
}

\frame{
\frametitle{Data Dependency Analysis}
 {\bf OCP Analysis}\\
Data dependency of the predicates of a partially covered branch statements on
\begin{itemize}
\item The program inputs: these inputs are declared as OCP's
\item Fields of the program inputs: Covana constructs a field declaration hierarchy up to program input
\end{itemize}
{\bf field declaration hierarchy}\\
\begin{itemize}
\item Use reflection to get the class structure
\item Use path conditions
\end{itemize}

}
\frame{
\frametitle{Data Dependency Analysis}
\begin{columns}
\column{.6\textwidth}
\begin{tabular}{c} 
\lstinputlisting[basicstyle=\ssmall, numbersep=10pt]{ocpExample.java}
\end{tabular}
\column{.4\textwidth}
{\scriptsize
\[ FixedSizeStack s3 = new \wedge \]
\[Stack s2 = s2.stack \wedge \]
\[List <object> s1 = s2.items \wedge \]
\[int s0 = s1.size \wedge \]
\[s0 == 10\]
}
\end{columns}
FixedSizeStack\\
\hspace{2cm}$\llcorner$\hspace{0.5cm}FixedSizestack.stack\\
\hspace{4.5cm}$\llcorner$\hspace{1cm}Stack.items
}

\frame{
\frametitle{Data Dependency Analysis}
{\bf Analyzing field declaration hierarchy}\\
\begin{tabular}{c} 
\lstinputlisting[basicstyle=\ssmall, numbersep=10pt]{ddaAlgorithm.java}
\end{tabular}
}

\section{Results}
\subsection{}
\frame{
\frametitle{Evaluation}
{\bf Evaluation criteria depending on}\\
\begin{itemize}
\item{Efficiency in identifying EMCPs \& OCPs }\\
\item{Efficiency in pruning irrelevant problem candidates }\\
\end{itemize}
{\bf Subjects of evaluation}\\
\begin{itemize}
\item{PEX:as a DSE test-generation tool}\\

\end{itemize}
\hspace{3.3 mm}Two popular .NET applications
\begin{itemize}
\item{xUnit: 223 classes \& interfaces, 11.4 KLOC}\\
\item{QuickGraph: c\# graph library, 165 classes, 8.3 KLOC }\\

\end{itemize}
}
\subsection{}
\frame{
\frametitle{Evaluation results}
\begin{table}
\scalebox{0.7}{
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | }
\hline
\multirow{2}{*}{\# File} &
  \multicolumn{4}{|c|}{Object-Creation Problem (OCP)} &
  \multicolumn{4}{|c|}{External-Method-Call Problem (EMCP)} \\
\cline{2-9}
   & \# Identified & \# Real & \# FP & \# FN & \# Identified & \# Real & \# FP & \# FN \\
\hline
  242 & 155 & 165 & 20 & 30 & 43 & 44 & 1 & 2\\
\hline
\end{tabular}}
\caption{Efficiency in identifying EMCPs \& OCPs}
\end{table}
\begin{table}
\scalebox{0.65}{
\begin{tabular}{| c | c | c | c | c | c | c | c | c | c | }
\hline
  \multicolumn{5}{|c|}{Object-Creation Problem (OCP)} &
  \multicolumn{5}{|c|}{External-Method-Call Problem (EMCP)} \\
\hline
   \# Cand & \# Ident & \# Pruned & \# FP & \# FN & \# Cand & \# Ident & \# Pruned & \# FP & \# FN \\
\hline
451 & 155 & 296 (65.63\%) & 20 & 30 & 1610 & 43 & 1567 (97.33\%) & 1 & 2\\
\hline
\end{tabular}}
\caption{Efficiency in pruning irrelevant problem candidates}
\end{table}
}
\section{Assessment}
\subsection{}
\frame{
\frametitle{Conclusions}
{\bf Covana:}\\
\begin{itemize}
\item Helps developers in locating serious reasons for low structural coverage
\item Identifies problems (EMCP, OCP) faced by structural test-generation tools 
\item Uses data dependency of partially covered branch statements on problem candidates, to prune irrelevant candidates
\end{itemize}
}


\subsection{}
\frame{
\frametitle{}
\begin{center}
\vspace{1.5cm}
{\bf \LARGE Thank you!}\\
\vspace{0.75cm}
{\large any questions...?}
\end{center}
}

\appendix 

\section{Extra}
\subsection{}
\frame{
\frametitle{Future work}
\begin{itemize}
\item{Assisting other structural Test-Generation approaches }\\
\item{Dealing with static fields, by assigning symbolic values to them}\\
\item{Dealing with External method calls who's arguments are concrete values}\\
\end{itemize}
}

\subsection{}
\frame{
\frametitle{Related works}

 {\bf Residual test coverage monitoring}$^{\textbf{{[}5{]}}}$\\
\begin{itemize}
\item {Residual coverage monitoring tool for java}\\
\item {Doesn't provide a way to analyze the coverage}\\
\end{itemize}
 {\bf Explaining failures of program analysis}$^{\textbf{{[}6{]}}}$\\
\begin{itemize}
\item {Express arbitrary data flow analysis using analysis language and compute reasons for the failures}\\
\item {We focus on a different problem and include different techniques to identify problems of achieving high structural coverage}
\end{itemize}
}

\frame{
\frametitle{Related works Cont.}
 {\bf Type-Dependence Analysis and Program Transformation for Symbolic Execution}$^{\textbf{{[}7{]}}}$\\
\begin{itemize}
\item {Identify EMCP's that are problematic in symbolic execution using static analysis depending on checking the arguments for symbolic values}\\
\item {We use data dependency of arguments of external method calls on program inputs, as well as data dependencies of partially covered branch statements on external method calls for their return values}\\
\end{itemize}
}

\frame{
\frametitle{References}
\begin{tabular}{ l  l }
\textbf{{[}1{]}} & National Institute of Standards and technology\\
\textbf{{[}2{]}} & Structural Coverage Metrics,  IPL Information Processing Ltd.\\
\textbf{{[}3{]}} & Elfriede Dustin, et al.: Automated Software Testing.\\&Addison Wesley, 1999, ISBN 0-20143-287-0\\
\textbf{{[}4{]}} & Example based on \\&http://en.wikipedia.org/wiki/Concolic\_testing\\
\textbf{{[}5{]}} & C. Pavlopoulou and M. Young\\
\textbf{{[}6{]}} & D. von Dincklage and A. Diwan\\
\textbf{{[}7{]}} & S. Anand, A. Orso, and M. J. Harrold\\
\end{tabular}
}

\end{document}
